/*
 * @lc app=leetcode.cn id=652 lang=javascript
 *
 * [652] 寻找重复的子树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
// 使用栈模拟序列递归
var findDuplicateSubtrees = function(root) {
  let map = new Map()
  // 使用栈遍历树
  let stack = []
  // 记录有右子树的节点的左子树序列
  let leftSqlize = []
  // 记录当分支的序列
  let s = ''
  let cur = root
  let res = []
  let prev = null
  while (stack.length || cur) {
    while (cur) {
      stack.push(cur)
      cur = cur.left
    }
    cur = stack.pop()
    // 叶子节点
    if (!cur.right) {
      let str = '-'
      if (!cur.left) str += ',-'
      if (!s) {
        s = `${str},${cur.val}`
      } else {
        s += `${str},${cur.val}`
      }
      let m = map.get(s)
      if (!m) {
        map.set(s, 1)
      } else if (m === 1) {
        res.push(cur)
        map.set(s, 2)
      }
      prev = cur
      cur = null
    } else if (cur.right === prev) {
      // 右节点完全访问
      let leftS = leftSqlize.pop()
      s += `,${leftS},${cur.val}`
      let m = map.get(s)
      if (!m) {
        map.set(s, 1)
      } else if (m === 1) {
        res.push(cur)
        map.set(s, 2)
      }
      prev = cur
      cur = null
    } else {
      // 有右节点
      stack.push(cur)
      leftSqlize.push(s)
      // 进入右分支,当前分支序列置空
      s = ''
      cur = cur.right
    }
  }
  return res
};
// @lc code=end

// 递归序列化
// var findDuplicateSubtrees = function(root) {
//   let map = new Map()
//   let res = []

//   const findId = (node) => {
//     if (!node) return '-'
//     let leftId = findId(node.left)
//     let rightId = findId(node.right)
//     let id = `${node.val},${leftId},${rightId}`
//     let m = map.get(id)
//     if (m === 1) {
//       res.push(node)
//       map.set(id, 2)
//     } else if (!m) {
//       map.set(id, 1)
//     }
//     return id
//   }
//   findId(root)
//   return res
// };

// 序列化作为键值
// var findDuplicateSubtrees = function(root) {
//   let map = new Map()
//   // 使用栈遍历树
//   let stack = []
//   let cur = root
//   let res = []
//   while (stack.length || cur) {
//     while (cur) {
//       stack.push(cur)
//       cur = cur.left
//     }
//     cur = stack.pop()
//     let s = sqlize(cur)
//     let m = map.get(s)
//     if (!m) {
//       map.set(s, 1)
//     } else if (m === 1) {
//       res.push(cur)
//       map.set(s, 2)
//     }
//     cur = cur.right
//   }
//   return res
// };

// var sqlize = function (root) {
//   let list = []
//   let bfs = [root]
//   while (bfs.length) {
//     const b = [...bfs]
//     bfs.length = 0
//     for (const tree of b) {
//       list.push(tree ? tree.val : tree)
//       if (tree) {
//         bfs.push(tree.left)
//         bfs.push(tree.right)
//       }
//     }
//   }
//   return list.join(',')
// }
